package innersort.select;

import innersort.speed.SortStrategy;

import java.util.Arrays;

/**
 * @ author : HyoJoo-W
 * @ createDate : 2021-06-05 14:07
 * @ Description : 堆排序,自下而上,自左向右(顺序 存储)
 */
public class HeapSort implements SortStrategy
{
    public static void main(String[] args)
    {
        int[] array = {4, 6, 8, 5, 9, -1};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }

    @Override
    public void sort(int[] array)
    {
        heapSort(array);
    }

    public static void heapSort(int[] array)
    {
        //自下而上,自左向右,调整为大顶堆
        //array.length / 2: 叶子节点数 ,减一后就是最下、最左的第一颗子树根节点在数组的索引
        for (int i = array.length / 2 - 1; i >= 0; i--)
        {
            adjustToBigTopHeap(array, i, array.length);
        }


        //j: 需要调整的次数(length - 1)
        for (int j = array.length - 1; j > 0; j--)
        {
            //2. 将最大元素下沉到数组尾
            int temp = array[j];
            array[j] = array[0];
            array[0] = temp;

            //3. 重新调整减少最大元素后的树
            adjustToBigTopHeap(array, 0, j);
        }
    }

    //将 i 对应的非叶子节点调整为大顶堆
    public static void adjustToBigTopHeap(int[] array, int i, int length)
    {
        //i: 非叶子节点在数组中的索引
        //length: 对length个节点调整
        int temp = array[i];//保存当前元素的值

        //k: i的左节点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1)
        {
            if (k + 1 < length && array[k] < array[k + 1])
            {
                //左节点 < 右节点
                k++;//k指向右节点(较大值)
            }
            if (array[k] > temp)
            {
                //子节点大于父节点
                array[i] = array[k];//第一次交换数组的值
                i = k;
            }
            else
            {
                break;
            }
        }
        // for 循环结束后,将以i 为父节点的树的最大值放在了顶部
        array[i] = temp;//第二次交换数组的值,将之前保存的顶部值给到array[i](如果i已经发生变化)
    }
}
